\documentclass[12pt, BCOR12mm, pdftex, DIV=calc, parskip=half]{scrartcl}

\usepackage[utf8]{inputenc}
\usepackage[ngerman]{babel}

\begin{document}
\section{Algorithmen}
Wir verwenden einen Algorithmus, der die Reihenfolge der Produkte verändert, um eine Nachbarlösung zu finden. Tritt lange keine Verbesserung auf, wird für eine gewisse Zeit ein weiterer Algorithmus aufgerufen. Durch diesen werden die Varianten einzelner Produkte getauscht. Nach dieser Zeit wird die gefundene Nachbarlösung als neue Lösung verwendet.

Verwendet werden die Beispieldaten aus dem StudIP.

Fügt man die Aufträge und Produkte in der Reihenfolge aus der Datei hinzu und wählt jeweils die erste Variante, ergibt sich ein Qualitätswert von 4871965. Wird stattdessen die Variante mit der kürzesten Produktionszeit gewählt, ergibt sich ein signifikant besserer Wert von 1687771. Durch sortieren der Aufträge nach Earliest-Deadline-First, kann der ursprüngliche Plan weiter auf den Wert 291165 verbessert werden.

Im Folgenden vergleichen wir auf Basis des obigen Algorithmus einen Threshold- und einen Sintflut-Algorithmus. Im Initialplan sind die Aufträge nach EDF sortiert und es wird stets die Variante mit der kürzesten Produktionszeit gewählt.
\section{Welcher Ihrer Algorithmen kommt schneller zu guten Ergebnissen?}
In unseren Testreihen kam der Sintflut-Algorithmus schneller zu guten Ergebnissen. Nach 30 Sekunden konnte er den ursprünglichen Plan durchschnittlich um 5\% verbessern, während der Threshold-Algorithmus nur eine Verbesserung von 2,5\% erreicht.
Nach 2 Minuten zeigt sich ein anderes Bild: Der Sintflut-Algorithmus erreicht im Schnitt 18\% Verbesserung, der Threshold-Algorithmus gar 21\%. 
Auch nach einer halben Stunde behält der Threshold-Algorithmus im Schnitt die Nase vorn: Er verbessert den üblichen Plan um knapp 99\%, während der Sintflut-Algorithmus durchschnittlich nur eine Verbesserung von 94\% erreicht.
\section{Welcher Ihrer Algorithmen braucht pro Schritt am meisten Rechenzeit?}
Beide Algorithmen brauchen etwa die gleiche Zeit pro Iteration: 400 - 500 ms auf unserem Testsystem. Außerdem wird in einigen Iterationen der Varianten-Algorithmus aufgerufen, der ebenfalls 400 - 500 ms pro Iteration benötigt. Dies scheint beim Sintflut-Algorithmus häufiger der Fall zu sein, offensichtlich findet er bei steigendem Wasserstand also seltener eine akzeptable Nachbarlösung als der Threshold-Algorithmus.
\section{Wie viele Iterationen brauchen Sie durchschnittlich bei großen Datenmengen für gute Ergebnisse?}
Wir nehmen an, dass der initiale Plan bereits ein gutes Ergebnis liefert, dass mit den iterativen Algorithmen nur noch verbessert wird. Wir vergleichen die Anzahl Iterationen die beide Algorithmen brauchen, um den Ausgangsplan um 25\% zu verbessern:
Der Sintflut-Algorithmus benötigt im Schnitt etwa 220 Iterationen, der Threshold-Algorithmus lediglich 180 Iterationen. Dies bestätigt das Bild über den schnellen Fortschritt der Algorithmen: Während der Sintflut-Algorithmus zu Beginn schneller durch den Lösungsraum kommt, wird er nach kurzer Zeit vom Threshold-Algorithmus überholt.
\section{Allgemeine Beobachtungen}
Unsere iterativen Algorithmen bieten die Möglichkeit, auch gute Pläne Schritt für Schritt zu verbessern, benötigen dafür jedoch relativ viel Zeit. Das Vorsortieren der Aufträge und die Auswahl der passenden Varianten bringt - gemessen an der Rechenzeit, die in etwa der Zeit für eine Iteration entspricht - eine deutlich größere Verbesserung der Planqualität. Natürlich lässt sich diese Steigerung nur bis zu einem gewissen Grad betreiben. Das Mittel der Wahl scheint also zu sein, mit einer guten Heuristik einen sehr guten Initialplan zu erzeugen, der mit zeitraubenden iterativen Verfahren nur noch verfeinert wird.
\end{document}

